Within the field of cryptography, it is well recognized that the strength of any cryptographic system depends, among other things, on the key distribution technique employed. For conventional encryption to be effective, such as a symmetric key system, two communicating parties must share the same key and that key must be protected from access by others. The key must, therefore, be distributed to each of the parties.
FIG. 1 shows one form of a conventional existing key distribution process. As shown in FIG. 1, for a party, Bob, to decrypt ciphertext encrypted by a party, Alice, Alice or a third party must share a copy of the key with Bob. This distribution process can be implemented using a number of known methods including the following: 1) Alice can select a key and physically deliver the key to Bob; 2) a third party can select a key and physically deliver the key to Bob; 3) if Alice and Bob both have an encrypted connection to a third party, the third party can deliver a key on the encrypted links to Alice and Bob; 4) if Alice and Bob have previously used an old key, Alice can transmit a new key to Bob by encrypting the new key with the old; and 5) Alice and Bob may agree on a shared key via a one-way mathematical algorithm, such as Diffie-Hellman key agreement.
All of these distribution methods are vulnerable to interception of the distributed key by an eavesdropper, Eve, or by Eve “cracking” the supposedly one-way algorithm. Eve can eavesdrop and intercept or copy a distributed key and then subsequently decrypt any intercepted ciphertext that is sent between Bob and Alice. In existing cryptographic systems, this eavesdropping may go undetected, with the result being that any ciphertext sent between Bob and Alice is compromised.
To combat these inherent deficiencies in the key distribution process, researchers have developed a key distribution technique called quantum cryptography. Quantum cryptography employs quantum systems and applicable fundamental principles of physics to ensure the security of distributed keys. Heisenberg's uncertainty principle mandates that any attempt to observe the state of a quantum system will necessarily induce a change in the state of the quantum system. Thus, when very low levels of matter or energy, such as individual photons, are used to distribute keys, the techniques of quantum cryptography permit the key distributor and receiver to determine whether any eavesdropping has occurred during the key distribution. Quantum cryptography, therefore, prevents an eavesdropper, like Eve, from copying or intercepting a key that has been distributed from Alice to Bob without a significant probability of Bob's or Alice's discovery of the eavesdropping.
An existing quantum key distribution (QKD) scheme involves a quantum channel, through which Alice and Bob send keys using polarized or phase encoded photons, and a public channel, through which Alice and Bob send ordinary messages. Since these polarized or phase encoded photons are employed for QKD, they are often termed QKD photons. The quantum channel is a path, such as through air or an optical fiber, that attempts to minimize the QKD photons' interaction with the environment. The public channel may comprise a channel on any type of communication network, such as a Public Switched Telephone network, the Internet, or a wireless network.
An eavesdropper, Eve, may attempt to measure the photons on the quantum channel. Such eavesdropping, however, will induce a measurable disturbance in the photons in accordance with the Heisenberg uncertainty principle. Alice and Bob use the public channel to discuss and compare the photons sent through the quantum channel. If, through their discussion and comparison, they determine that there is no evidence of eavesdropping, then the key material distributed via the quantum channel can be considered completely secret.
FIGS. 2 and 3 illustrate an existing scheme 200 for quantum key distribution in which the polarization of each photon is used for encoding cryptographic values. To begin the quantum key distribution process, Alice generates random bit values and bases 205 and then encodes the bits as polarization states (e.g., 0°, 45°, 90°, 135°) in sequences of photons sent via the quantum channel 210 (see row 1 of FIG. 3). Alice does not tell anyone the polarization of the photons she has transmitted. Bob receives the photons and measures their polarization along either a rectilinear or diagonal basis that is randomly selected with substantially equal probability. Bob records his chosen basis (see row 2 of FIG. 3) and his measurement results (see row 3 of FIG. 3).
Bob and Alice discuss 215, via the public channel 220, which basis he has chosen to measure each photon. Bob, however, does not inform Alice of the result of his measurements. Alice tells Bob, via the public channel, whether he has made the measurement along the correct basis (see row 4 of FIG. 3). In a process called “sifting” 225, both Alice and Bob then discard all cases in which Bob has made the measurement along the wrong basis and keep only the ones in which Bob has made the measurement along the correct basis (see row 5 of FIG. 3).
Alice and Bob then estimate 230 whether Eve has eavesdropped upon the key distribution. To do this, Alice and Bob must agree upon a maximum tolerable error rate. Errors can occur due to the intrinsic noise of the quantum channel and eavesdropping attack by a third party. Alice and Bob choose randomly a subset of photons m from the sequence of photons that have been transmitted and measured on the same basis. For each of the m photons, Bob announces publicly his measurement result. Alice informs Bob whether his result is the same as what she had originally sent. They both then compute the error rate of the m photons and, since the measurement results of the m photons have been discussed publicly, the polarization data of the m photons are discarded. If the computed error rate is higher than the agreed upon tolerable error rate (typically no more than about 15%), Alice and Bob infer that substantial eavesdropping has occurred. They then discard the current polarization data and start over with a new sequence of photons. If the error rate is acceptably small, Alice and Bob adopt the remaining polarizations, or some algebraic combination of their values, as secret bits of a shared secret key 235, interpreting horizontal or 45 degree polarized photons as binary 0's and vertical or 135 degree photons as binary 1's (see row 6 of FIG. 3).
Alice and Bob may also implement an additional privacy amplification process 240 that reduces the key to a small set of derived bits to reduce Eve's knowledge of the key. If, subsequent to discussion 215 and sifting 225, Alice and Bob adopt n bits as secret bits, the n bits can be compressed using, for example, a hash function. Alice and Bob agree upon a publicly chosen hash function ƒ and take K=ƒ(n bits) as the shared r-bit length key K. The hash function randomly redistributes the n bits such that a small change in bits produces a large change in the hash value. Thus, even if Eve determines a number of bits of the transmitted key through eavesdropping, and also knows the hash function ƒ, she still will be left with very little knowledge regarding the content of the hashed r-bit key K. Alice and Bob may further authenticate the public channel transmissions to prevent a “man-in-the-middle” attack in which Eve masquerades as either Bob or Alice.
Sifting is described in the paper, “Quantum Cryptography: Public Key Distribution and Coin Tossing,” by Charles H. Bennett and Giles Brassard, International Conference on Computers, Systems & Signal Processing, December 1984. A known variation on sifting, called the Geneva protocol, provides protection against an eavesdropping attack, called a photon-number splitting attack. The Geneva protocol is described in, “Quantum Cryptography Protocols Robust Against Photon Number Splitting Attacks,” by V. Scarani, A. Acin, G. Ribordy, N. Ribordy and N. Gisin, ERATO Conference on Quantum Information Science 2003, Sep. 4-6, 2003, Niijima-kaikan, Kyoto Japan. In existing sifting protocols, both parties select a ‘basis’ for each light pulse, but only one of the parties contributes a ‘value.’ For example, in the sifting protocols discussed above, a one-way system is described. In one-way systems and plug and play systems, one party may contribute the ‘value.’ In a typical quantum system based on entanglement, a source of entangled photons contributes the ‘value’ (automatically by the physical process that produces entangled pairs).
To ensure that the party contributing the ‘value’ does so in a random fashion, the contributing party must continually monitor its random sequences to check for bias. If bias is found, the contributing party either compensates for any observed bias or, when the bias is too severe for compensation, the contributing party may shut down the system. The bias monitoring, in general, is rather crude and it is quite possible that a party's random number generator may exhibit patterns of bias that are not detected by any checking procedure. Such patterns will degrade the quality of the cryptographic key produced by the system because any pattern to the randomness decreases the entropy of the key material. Furthermore, low-quality cryptographic key material may be produced for some time before subtle patterns of bias are detected.
Existing, non-quantum cryptographic systems perform a bias check. In addition, however, these non-quantum systems often obtain randomness by combining random number inputs from two different parties under the assumption that if one or both parties' random number generators are biased, in general, these problems will not be correlated. For example, in an existing Diffey-Hellman key agreement technique, each party (Alice and Bob) independently formulates a random number. A distributed calculation uses the two random numbers to determine a shared key. Thus, proper combination of two generators may lead to randomness of a higher quality than use of a single random number generator alone.
A quantum cryptographic system that allows multiple parties to contribute random values for the quantum key distribution process is needed in order to decrease the probability of generating biased cryptographic keys.